#!/usr/bin/env python3
# -*- encoding: utf-8 -*-

def quick_sort(arr):
    """快速排序（递归实现）"""
    if len(arr) <= 1:
        return arr
    
    # 选择枢值（三种策略）
    pivot = select_pivot(arr)  # 调用枢值选择函数
    
    # 分区操作
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 递归排序并合并
    return quick_sort(left) + middle + quick_sort(right)

def select_pivot(arr):
    """选择枢值的三种策略（任选其一）"""
    # 策略1：固定选择第一个元素（简单但可能低效）
    # return arr[0]
    
    # 策略2：随机选择（避免最坏情况）
    # import random
    # return random.choice(arr)
    
    # 策略3：三数取中法（平衡性能）
    left, right = 0, len(arr) - 1
    mid = (left + right) // 2
    a, b, c = arr[left], arr[mid], arr[right]
    if a <= b <= c or c <= b <= a:
        return b
    elif b <= a <= c or c <= a <= b:
        return a
    else:
        return c

# 测试代码
if __name__ == "__main__":
    data = [64, 34, 25, 12, 22, 11, 90, 54, 7, 3]
    print("排序前:", data)
    sorted_data = quick_sort(data)
    print("排序后:", sorted_data)
